//class Solution {
//public:
//    int missingNumber(vector<int>& nums) {
//        int n = nums.size(), ret = 0;
//        for (int i = 1; i <= nums.size(); i++)
//            ret ^= i;
//        for (auto num : nums)
//            ret ^= num;
//        return ret;
//    }
//};




class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].size() == 0) return false;
        int m = matrix.size(), n = matrix[0].size();
        if (matrix[0][0] > target || matrix[m - 1][n - 1] < target) return false;
        int i = 0, j = n - 1;
        while (i < m && j >= 0)
        {
            if (matrix[i][j] < target) i++;
            else if (matrix[i][j] > target) j--;
            else return true;
        }
        return false;
    }
};